//
//
//class LRUCache {
//
//    class ListNode {
//        int key;
//        int val;
//        ListNode prev;
//        ListNode next;
//
//        public ListNode(int key, int val) {
//            this.key = key;
//            this.val = val;
//        }
//    }
//
//    ListNode head = new ListNode(-1, -1);
//    ListNode tail = new ListNode(-1, -1);
//    Map<Integer, ListNode> hash = new HashMap<>();
//    int size;
//
//    public LRUCache(int capacity) {
//        this.size = capacity;
//        head.next = tail;
//        head.prev = tail;
//        tail.prev = head;
//        tail.next = head;
//    }
//
//    public int get(int key) {
//        if (!hash.containsKey(key)) {
//            return -1;
//        }
//
//        ListNode node = hash.get(key);
//        remove(node);
//        add(node);
//
//        return node.val;
//    }
//
//    public void put(int key, int value) {
//        if (!hash.containsKey(key)) {
//            ListNode node = new ListNode(key, value);
//            add(node);
//            hash.put(key, node);
//        } else {
//            ListNode node = hash.get(key);
//            node.val = value;
//            remove(node);
//            add(node);
//        }
//        if (hash.size() > size) {
//            hash.remove(tail.prev.key);
//            remove(tail.prev);
//        }
//
//
//    }
//
//    public void remove(ListNode node) {
//        ListNode prev = node.prev;
//        ListNode next = node.next;
//        prev.next = next;
//        next.prev = prev;
//    }
//
//    public void add(ListNode node) {
//        // 头插尾删
//        ListNode next = head.next;
//        node.next = next;
//        node.prev = head;
//
//        next.prev = node;
//        head.next = node;
//    }
//}